Sissoko được sinh ra ở Le Blanc-Mesnil, Seine-Saint-Denis, có bố mẹ là người Mali. Cha anh là một công nhân xây dựng và mẹ anh là một bà nội trợ. Sissoko là con cả trong gia đình có bốn người con, có ba em gái. Anh bị thu hút bởi bóng đá khi còn rất trẻ, anh nói rằng: "Tôi nhanh chóng nhận ra rằng bóng đá có thể giúp tôi có một cuộc sống tốt hơn". Năm sáu tuổi, Sissoko gia nhập học viện đào tạo trẻ của Espérance Aulnay, có trụ sở ở gần Aulnay-sous-Bois, một vùng ngoại ô ở phía đông bắc Paris. Anh được đào tạo ba lần một tuần tại câu lạc bộ dưới sự giám sát của huấn luyện viên Adama Dieye, người hiện đang làm phóng viên cho đội futsal của câu lạc bộ. Sissoko mô tả Dieye như một người cố vấn quan trọng trong quá trình phát triển tài năng của mình rằng "Tôi ở đây hôm nay là vì có ông ấy". Vào tháng 7 năm 1999, Sissoko chuyển đến Saint-Ouen để gia nhập AS Red Star 93. Sissoko đã trải qua hai năm làm việc tại câu lạc bộ và là đồng đội với tiền vệ của Guingamp, Yannis Salibur. Vào tháng 9 năm 2001, anh trở lại Aulnay thêm hai năm để phát triển trước khi tìm cách gia nhập một câu lạc bộ chuyên nghiệp.